#include <time.h>
#include "Heap.h"

void  TestHeap1()
{
    int arr[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
    HP hp;
    HeapInit(&hp);
    for(int i = 0;i < sizeof(arr) / sizeof(int);i++)
    {
        HeapPush(&hp,arr[i]);
    }
    HeapPrint(&hp);

    //topK
    int k = 5;
    while(k--)
    {
        printf("%d",HeapTop(&hp));
        HeapPop(&hp);
    }

    HeapDestroy(&hp);
}

void HeapSort(int* a, int n)
{
    for (int i = ( n - 1 - 1 ) / 2;i >= 0;i--)
    {
        AdjustDown(a, n, i);
    }

    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}
/*
先建大堆，
首先将堆顶元素（在数组中索引为0处）与堆中最后一个元素（在数组中索引为end处，初始值为n-1）交换位置。
然后对剩余的元素（即除了已经交换到末尾的元素外）进行向下调整，重新构建大顶堆。
每次交换并调整完毕后，将 end 减一，表示当前堆中最大值已经就位，不再参与后续的比较和调整。
重复这个过程直到所有元素都被取出并排序完成。
*/



//topK问题
void TestHeap2()
{
    int n, k;
    printf("请输入n和k:>");
    scanf("%d%d", &n, &k);
    srand(time(0));
    FILE* fin = fopen("data.txt","w");
    if (fin == NULL)
    {
        perror("fopen fail");
        return;
    }

    int randK = k;
    for (size_t i = 0; i < n; ++i)
    /*  
        在C语言中，size_t 是一种无符号整数类型，它是由标准库中的 <stddef.h> 或 <stdlib.h> 头文件
    定义的，专门用来表示对象的大小或者数组的索引。由于 size_t 能够足够地表示内存中可寻址的最大范围
    ，所以常用于数组索引和循环计数器，以保证可以处理大型数据集合。
        在这段代码 for (size_t i = 0; i < n; ++i) 中，使用 size_t 作为循环变量的类型是为了确保变量
     i 能够安全地表示从0到 n-1 的所有可能值，其中 n 是一个整数，表示数组的长度或要处理的元素数量。
     这样做可以避免因为 n 的值超过了有符号整型的最大值而导致的潜在整数溢出问题。
        使用 size_t 还有一个原因是，它与数组和指针运算保持一致性。例如，sizeof 运算符返回的类型就
    是 size_t，标准库中处理数组和内存的函数（如 malloc, calloc, memcpy, strlen 等）的参数和返回
    值也通常是 size_t 类型。因此，使用 size_t 可以提高代码的可移植性和正确性。
    */
    {
        int val = rand() % 100000;
        fprintf(fin, "%d\n",val);
    }

    fclose(fin);

    //找topK
    FILE* fout = fopen("data.txt","r");
    int* minHeap = malloc(sizeof(int)*k);

    if (fout == NULL)
    {
        perror("malloc fail!");
        return;
    }
    for (int i = 0; i < k; i++)
    {
        fscanf(fout, "%d",&minHeap[i]);
    }

    //建小堆,把另外n - k个元素依次和堆顶元素相比，比堆顶元素大则换进去，最后得到最大k个
    for (int i = ( n - 1 - 1 ) / 2;i >= 0;i--)
    {
        AdjustDown(minHeap, n, i);
    }

    int val = 0;
    while (fscanf(fout, "%d", &val) != EOF)
    {
        if (val > minHeap[0])
        {
            minHeap[0] = val;
            AdjustDown(minHeap, k, 0);
        }
    }

    for (int i = 0; i < k; ++i)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");

	fclose(fout);

}